/*
https://leetcode-cn.com/problems/132-pattern/solution/132mo-shi-by-leetcode-solution-ye89/
 */
import java.util.Stack;

public class Solution456 {
    public boolean find132pattern(int[] nums) {
        Stack<Integer> stack=new Stack<>();
        stack.push(nums[nums.length-1]);
        int max=Integer.MIN_VALUE;
        for (int i=nums.length-2;i>=0;i--){
            if (nums[i]<max){
                return true;
            }
            while (!stack.empty() && nums[i]>stack.peek()){
                max=Math.max(max,stack.pop());
            }
            if (nums[i]>max){
                stack.push(nums[i]);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(new Solution456().find132pattern(new int[]{3,1,4,2}));
    }
}
